// https://www.lintcode.com/problem/next-greater-element-ii/description?_from=ladder&&fromId=86

class Solution {
public:
    /**
     * @param nums: an array
     * @return: the Next Greater Number for every element
     */
    vector<int> nextGreaterElements(vector<int> &nums) {
        // int len = nums.size();
        // nums.insert(nums.end(), nums.begin(), nums.end());
        // vector<int> record(len * 2, -1);
        // 错的，算了最小的比它大的数，会把之前记录的覆盖掉
        // for (int i = record.size() - 2; i >= 0; --i)
        // {
        //     if (record[i + 1] > nums[i] || nums[i + 1] > nums[i])
        //     {
        //         if (nums[i + 1] > nums[i])
        //             if (record[i + 1] > nums[i])
        //                 record[i] = min(record[i + 1], nums[i + 1]);
        //             else record[i] = nums[i + 1];
        //         else record[i] = record[i + 1];
        //     }
        // }
        // for (int r: record)
        // {
        //     cout << r << endl;
        // }
        // vector<int> result(record.begin(), record.begin() + len);
        
        //法一：双循环向后找大的
        // int len = nums.size();
        // vector<int> record(len, -1);
        // for (int i = 0; i < len; ++i)
        // {
        //     for (int j = i + 1; j < len * 2; ++j)
        //     {
        //         if (nums[j % len] > nums[i])
        //         {
        //             record[i] = nums[j % len];
        //             break;
        //         }
        //     }
        // }
        
        //法二：stack向前找
        stack<int> idx;
        int len = nums.size();
        vector<int> result(len, -1);
        for (int i = 0; i < len * 2; ++i)
        {
            int num = nums[i % len];
            while (!idx.empty() && nums[idx.top()] < num)
            {
                result[idx.top()] = num;
                idx.pop();
            }
            if (i < len) idx.push(i);
        }
        return result;
    }
};